package demo2;

import java.util.*;

public class Solution {

    //
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for(int bill : bills){
            if(bill == 5){
                five++;
            }else if(bill == 10){
                if(five == 0) { return false;}
                five--;
                ten++;
            }else{
                if(five > 0 && ten > 0){
                    five--;
                    ten--;
                }else{
                    if(five < 3) { return false;}
                    five -= 3;
                }
            }
        }
        return true;
    }

    //
    public int halveArray(int[] nums) {
        PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));
        double sum = 0;
        for(int x : nums){
            sum += x;
            heap.offer((double) x);
        }
        sum /= 2;

        int count = 0;
        while(sum > 0){
            double tmp = heap.poll() / 2.0;
            sum -= tmp;
            count++;
            heap.offer(tmp);
        }
        return count;
    }

    //
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for(int i = 0; i < n; i++){
            strs[i] = "" + nums[i];
        }

        Arrays.sort(strs, (a, b) -> {
            return (b + a).compareTo(a + b);
        });

        StringBuffer ret = new StringBuffer();
        for(String s : strs){
            ret.append(s);
        }

        if(ret.charAt(0) == '0') { return "0";}
        return ret.toString();
    }

    //
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if(n < 2) { return n;}

        int ret = 0, left = 0;
        for(int i = 0; i < n - 1; i++){
            int right = nums[i + 1] - nums[i];
            if(right == 0) { continue;}

            if(left * right <= 0) { ret++;}
            left = right;
        }
        return ret + 1;
    }
}
